package code601_700.code90_100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0
 *
 * 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 输出：6
 * 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 *
 * 输入：grid = [[0,0,0,0,0,0,0,0]]
 * 输出：0
 */
public class _695maxAreaOfIsland {

    /**
     * 本来准备创建一个二维数组进行记录是否已访问，偷看了一眼题解。访问过的都置零妙啊
     *
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 48.63%     * 的用户
     * 内存消耗：     * 38 MB     * , 在所有 Java 提交中击败了     * 99.93%     * 的用户
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {
        int[] dx = {1,0,0,-1};
        int[] dy = {0,1,-1,0};

        int maxArea = 0;
        Queue<int[]> queue;
        int xLength = grid.length;
        int yLength = grid[0].length;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1){
                    int area = 1;
                    grid[i][j] = 0;
                    queue = new LinkedList<>();
                    queue.offer(new int[]{i,j});
                    while (!queue.isEmpty()){
                        int[] now = queue.poll();
                        for (int k = 0; k < 4; k++) {
                            int newx = now[0] + dx[k];
                            int newy = now[1] + dy[k];
                            if(newx>=0&&newy>=0&&newx<xLength&&newy<yLength&&grid[newx][newy]==1){
                                area++;
                                grid[newx][newy] = 0;
                                queue.offer(new int[]{newx,newy});
                            }
                        }
                    }
                    maxArea = maxArea>area?maxArea:area;
                }
            }
        }
        return maxArea;
    }
}
